function mergeSortedArrays(arr1: string[], arr2: string[]) {
    let result = []
    let i = 0
    let j = 0
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result.push(arr1[i])
            i++
        } else if (arr1[i] > arr2[j]) {
            result.push(arr2[j])
            j++
        } else {
            result.push(arr1[i])
            i++
            j++
        }
    }
    while (i < arr1.length) {
        result.push(arr1[i])
        i++
    }
    while (j < arr2.length) {
        result.push(arr2[j])
        j++
    }
    return result
}

// 所有数组元素放到一个数组，再去重也可以，只是效率低些
// 如果像算法题要求的，要保留所有重复的元素，则只能这样合并
export function mergeMultipleSortedArrays(arrays: string[][]) {
    if (arrays.length === 1) {
        return arrays[0]
    }
    let mid = Math.floor(arrays.length / 2)
    let left = arrays.slice(0, mid)
    let right = arrays.slice(mid)

    let leftResult = mergeMultipleSortedArrays(left)
    let rightResult = mergeMultipleSortedArrays(right)

    return mergeSortedArrays(leftResult, rightResult)
}
